package leetcode.code0126;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;

public class Solution extends Solution126 {
	Map<String, List<String>> ways;// 所有联通路径<原词,通配词列表> <通配词,原词列表>
	List<List<String>> ans;

	@Override
	public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
		ans = new ArrayList<>();// 答案
		if (!wordList.contains(endWord)) {// 没有endWord，肯定没戏唱
			return ans;
		}
		if (!wordList.contains(beginWord)) {
			wordList.add(beginWord);// 为了做路用,wordList初始化ways时，捎带脚给beginWord也做了。
		}
		ways = new HashMap<>();// 所有联通路径<原词,通配词列表> <通配词,原词列表>
		this.findWays(wordList);// 初始化ways
		Set<String> done = new HashSet<>();// 走过的路
		Queue<String> q = new LinkedList<>();// 宽优搜索队
		q.add(beginWord);// 起始点
		Map<String, List<List<String>>> record = new HashMap<>();
		while (!q.isEmpty()) {
			int size = q.size();// 当前层宽度
			Set<String> levelDone = new HashSet<>();
			while (size > 0) {// 宽搜这一层
				String from = q.poll();
				this.move(q, done, from, record, endWord, levelDone);// from词步入下一层
				size--;// 当前层数量-1
			}
			if (ans.size() != 0) {
				break;
			}
			done.addAll(levelDone);
		}
		return ans;
	}

	private void move(Queue<String> q, Set<String> done, String from, Map<String, List<List<String>>> record,
			String endWord, Set<String> levelDone) {
		List<String> links = ways.get(from);// 每个from原词，通过link通配词，连接到to原词上
		List<List<String>> list = null;// 这层的from，是之前层的to，将所有以from结尾的路径都取出来，备用
		if (record.containsKey(from)) {
			list = record.get(from);
		} else {
			List<String> l = new ArrayList<>();
			l.add(from);
			list = new ArrayList<>();
			list.add(l);
		}
		for (String link : links) {
			List<String> tos = ways.get(link);// 从原词from到原词to
			for (String to : tos) {
				if (endWord.equals(to)) {// 可达目的endword，记录答案
					ans.addAll(this.add2list(to, list));
				} else if (!done.contains(to)) {// 没达到目的，必须是之前层没走过的
					if (!levelDone.contains(to)) {// 之前没走过，当前层没走过，入队
						levelDone.add(to);// 没走过的变成走过，但是不能立马加到去过的done，对于这一层来讲，这个位置仍然是可达到的
						q.add(to);// 添加到宽优队中
					}
					// 追加to到list路径里
					List<List<String>> last = record.getOrDefault(to, new ArrayList<>());
					last.addAll(this.add2list(to, list));
					record.put(to, last);
				}
			}
		}
	}

	private List<List<String>> add2list(String to, List<List<String>> list) {
		List<List<String>> branch = new ArrayList<>();
		for (List<String> l : list) {
			List<String> tmp = new ArrayList<>(l);
			tmp.add(to);
			branch.add(tmp);
		}
		return branch;
	}

	// 初始化路ways变量
	private void findWays(List<String> wordList) {
		for (String from : wordList) {
			char[] cur = from.toCharArray();
			for (int i = 0; i < cur.length; i++) {// 原词的每一位变成通配词
				char c = cur[i];
				cur[i] = '*';// 变更i位
				this.add2ways(from, new String(cur));// 建立原词和通配词的路
				cur[i] = c;// 回溯
			}
		}
	}

	// 建立<原词,通配词列表> <通配词,原词列表>
	private void add2ways(String from, String link) {
		List<String> list = ways.getOrDefault(from, new ArrayList<>());
		list.add(link);
		ways.put(from, list);// 原词列表中添加一个通配词
		list = ways.getOrDefault(link, new ArrayList<>());
		list.add(from);
		ways.put(link, list);// 通配词列表中添加一个原词
	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();

	}

}
